package test;

import java.util.*;

class TreeNode {
   int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    TreeNode(int x) { val = x; }
  }

class ListNode {
    public ListNode(int val) {
        this.val = val;
    }

    int val;
    ListNode next = null;
  }
  class A{
     public void fun(){
         System.out.println("父类的方法");
     }

  }

public class Main {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>>res = new ArrayList<>();
        Deque<TreeNode>deque = new LinkedList<>();
        deque.offer(root);
        boolean flag = true;
        while (!deque.isEmpty()){
            int size = deque.size();
            ArrayList<Integer>list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                list.add(node.val);
                if (node.left != null){
                    deque.offer(node.left);
                }
                if (node.right != null){
                    deque.offer(node.right);
                }

            }
            if (flag){
                res.add(list);
                flag = false;
            }else {
                Collections.reverse(list);
                res.add(list);
                flag = true;
            }

        }
        return res;
    }
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if (head == null || head.next == null)return head;
        ListNode p = head;
        ListNode cur = null;
        while (p.next != null){
            cur = p.next;
            if (p.val == cur.val){
                cur = cur.next;
            }else {
                p.next = cur;
                p = p.next;
            }
        }
        return head;

    }
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        int n = cost.length;
        int []dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(cost[i - 1] + dp[i - 1] , cost[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

    public static void main(String[] args) {

    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null)return head2;
        if (head2 == null)return head1;
        Stack<Integer>stack1 = new Stack<>();
        Stack<Integer>stack2 = new Stack<>();
        putDate(stack1 , head1);
        putDate(stack2 , head2);
        ListNode head = null;
        int sum = 0;
        int carry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()){
            int x = stack1.isEmpty() ? 0 : stack1.pop();
            int y = stack2.isEmpty() ? 0 : stack2.pop();
            sum = x + y + carry;
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = head.next;

        }
        return head;


    }

    private void putDate(Stack<Integer> stack1, ListNode head) {
        if (head == null)return;
        while (head != null){
            stack1.push(head.val);
            head = head.next;
        }
    }
    public ListNode sortInList (ListNode head) {
        PriorityQueue<ListNode>queue = new PriorityQueue<>((a , b)->a.val - b.val);
        while (head != null){
            queue.offer(head);
            head = head.next;
        }
        ListNode newNode = new ListNode(-1);
        ListNode p = newNode;
        while (!queue.isEmpty()){
            p.next = queue.poll();
            p = p.next;
        }
        p.next = null;
        return newNode;

    }



}
